package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/23 19:10 星期二
 */
public class _141_环形链表 {


    /**
     * 快慢指针法，当快慢指针相遇，则必然有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        //定义快慢指针
        ListNode fast = head,slow = head;
        //当快指针和快指针的下一指向不为空，循环继续
        while (fast!=null && fast.next!=null){
            //快指针走两次、慢指针走一次
            fast = fast.next.next;
            slow = slow.next;
            //若快慢指针相等，说明有环
            if (fast == slow){
                return true;
            }
        }
        //跑出边界，无环
        return false;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
